package codeRandomThoughts.Test496下一个更大元素I;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;

class Solution2 {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //单调栈
        Stack<Integer> ms = new Stack<>();

        //建一个map,存储元素对应nums1[]中的下标
        //一定要用hashMap吗?
        //用数组的话 0 <= nums1[i], nums2[i] <= 10^4
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            map.put(nums1[i], i);
        }

        int[] res = new int[nums1.length];
        Arrays.fill(res, -1);

        for (int i = 0; i < nums2.length; i++) {
            while (!ms.isEmpty() && (nums2[i] > nums2[ms.peek()])) {
                //获取要弹出的元素
                int ele = nums2[ms.pop()];

                //如果map中包含此元素
                //获取此元素在nums1中对应的下标
                if (map.containsKey(ele)) {
                    Integer index = map.get(ele);
                    //收集结果
                    res[index] = nums2[i];
                }
            }

            //单调栈里存的还是下标
            ms.push(i);
        }

        return res;
    }
}
